# TODO: 备选数字有哪些？
numQueue = [1,2,3,4,5,6,7,8,9]
# 用来回溯的栈
resultStack = []
# TODO: check point的格子有哪些？
checkPoint = [2,5,6,7,8]

SIZE = 3

SUM = 3*sum(numQueue)//len(numQueue)

# TODO: 如何初始化棋盘？
def InitBoard():
    return [[0 for i in range(SIZE)] for j in range(SIZE)]

board = InitBoard()
print(board)

# TODO: 如何从索引转化为行列组合？
def GetRowColFromIndex(idx):
    return idx//3, idx%3
print(GetRowColFromIndex(2))

# TODO: 如何判断即将要放置的数字是否可以放在这个格子里？
# cur_index: 当前考察的格子的索引
# val: 当前打算放在格子里的数字
def IsFillingValueValid(cur_index, val):
    global checkPoint, board
    x, y=GetRowColFromIndex(cur_index)
    if not cur_index in checkPoint:
        print(cur_index,val,"ok")
        return True
    else:
        print(cur_index,val)
        if cur_index==2 or cur_index==5:
            if board[x][0]+board[x][1]+val==SUM:
                return True
        elif cur_index==6:
            if board[0][y]+board[1][y]+val==SUM and board[0][2]+board[1][1]+val==SUM:
                return True    
        elif cur_index==7:
            if board[0][y]+board[1][y]+val==SUM:
                return True
        elif cur_index==8:
            if board[0][y]+board[1][y]+val==SUM and board[x][0]+board[x][1]+val==SUM and board[0][0]+board[1][1]+val==SUM:
                return True  
    print("\(QAQ\)")  
    return False

# TODO：如何获取比传入数字大并且尽可能接近传入的数字，而且还没有使用过的数字？
# 如果找到合适的数字则返回它，否则就返回-1
def GetBiggerUnusedNum(num):
    print(num)
    while not num > 9:
        num += 1
        if num in numQueue:
            print(num)
            return num 
    return -1

# TODO: 遇到check point格子的时候，计算这个格子应该放什么数字
# 如果计算得到的数字在备选容器里,则返回它，否则返回-1
def CalcCheckPointNum(curIndex):
    global checkPoint, board
    global board, numQueue
    num=-1
    if curIndex==2:
        cp=SUM-board[0][0]-board[0][1]
        if cp in numQueue:
            num=cp
    elif curIndex==5:
        cp=SUM-board[1][0]-board[1][1]
        if cp in numQueue:
            num=cp
    elif curIndex==6:
        cp=SUM-board[0][0]-board[1][0]
        if cp in numQueue and cp+board[1][1]+board[0][2]==SUM:
            num=cp
    elif curIndex==7:
        cp=SUM-board[0][1]-board[1][1]
        if cp in numQueue:
            num=cp
    elif curIndex==8:
        cp=SUM-board[2][1]-board[2][0]
        if cp in numQueue and cp+board[1][1]+board[0][0]==cp+board[1][2]+board[0][2]==SUM:
            num=cp

    return num

# TODO: 向指定格子放置一个数字
# 放置一个数字的时候不是简单的修改board上对应行列的值，而有三件事要处理，想想看是那三件事
def PutNum(curIndex, num):
    global board,numQueue,resultStack
    x,y = GetRowColFromIndex(curIndex)
    board[x][y]=num
    resultStack.append((curIndex,num))
    numQueue.remove(num)

def main():
    global board, numQueue
    # 当前要填的格子    
    curIndex = 0

    while len(numQueue) > 0:
        # 如果index in checkPoint，则自动补最后一个数字
        r, c = GetRowColFromIndex(curIndex)
        # 是否需要回溯的标志
        needRollBack = False
        print(curIndex," new start")
        if board[r][c]==0:
            # TODO：如果考察的格子为空格，应该进行哪些处理？
            num=min(numQueue)
            if IsFillingValueValid(curIndex,num)==True:
                PutNum(curIndex,num)
            else:
                m = CalcCheckPointNum(curIndex)
                if m==-1:
                    needRollBack=True
                else:
                    PutNum(curIndex,m)

            if needRollBack==True:
                # TODO：如果需要回溯的时候，需要做那些处理？              
                while True:
                    out=resultStack.pop()
                    temp=out[0]
                    num=out[1]
                    x1,y1 = GetRowColFromIndex(temp)
                    numQueue.append(num)
                    next=GetBiggerUnusedNum(num)
                    if next!=-1:
                        PutNum(temp, next)
                        break
                    board[x1][y1]=0
                curIndex=temp+1
            else:
                # TODO：不需要回溯的时候，需要做那些处理？
                curIndex+=1

    # TODO：输出找到的九宫格组合：
    for i in board:
        print(i)

main()